//下一个更大元素
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) 
    {
        vector<int>res(nums1.size(),-1);
        unordered_map<int,int>hash;
        for(int i=0;i<nums1.size();i++)
        {
            hash[nums1[i]]=i;
        }
        stack<int>st;
        st.push(0);
        for(int i=1;i<nums2.size();i++)
        {
            if(nums2[i]<=nums2[st.top()])
            {
                st.push(i);
            }
            else
            {
                while(!st.empty() && nums2[i]>nums2[st.top()])
                {
                    if(hash.find(nums2[st.top()])!=hash.end())
                    {
                        int index=hash[nums2[st.top()]];
                        res[index]=nums2[i];
                    }
                    st.pop();
                }
                st.push(i);
            }
        }
        return res;
    }
};
//每日温度
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) 
    {
        stack<int>st;
        st.push(0);
        int n=temperatures.size();
        vector<int>res(n,0);
        for(int i=1;i<n;i++)
        {
            if(temperatures[i]<=temperatures[st.top()])
            {
                st.push(i);
            }
            else
            {
                while(!st.empty() && temperatures[i]>temperatures[st.top()])
                {
                    res[st.top()]=i-st.top();
                    st.pop();
                }
                st.push(i);
            }
        }
        return res;
    }
};
//复写零
class Solution {
public:
    void duplicateZeros(vector<int>& arr) 
    {
        // 1. 先找到最后⼀个数
        int cur = 0, dest = -1, n = arr.size();
        while(cur < n)
        {
            if(arr[cur]) dest++;
            else dest += 2;
            if(dest >= n - 1) break;
            cur++;
        }
        // 2. 处理⼀下边界情况
        //dest==n的情况 一定是在n-2这个位置 cur指向0了
        //一次性向后走了两步导致越界
        if(dest == n)
        {
            arr[n - 1] = 0;
            cur--; dest -=2;
        }
        // 3. 从后向前完成复写操作
        while(cur >= 0)
        {
            if(arr[cur]) arr[dest--] = arr[cur--];
            else
            {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
    }
};